package Leetcode.树;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author: kirito
 * @Date: 2024/3/3 18:21
 * @Description:
 * 二叉搜索树具有如下性质：
 *
 * 结点的左子树只包含小于当前结点的数。
 *
 * 结点的右子树只包含大于当前结点的数。
 *
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树；在访问其左子树和右子树时，我们也按照同样的方式遍历；直到遍历完整棵树。
 *
 */

public class 二叉搜索树中第K小的元素 {
    /**
     * 感觉不太好理解思路，干脆中序遍历加到数组，然后找K
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            //遍历到最小的一个节点   即最左边
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            --k;
            if (k == 0) {
                break;
            }
            //如果没有找到第K小，的就去遍历右子树（现在已经在最左边最小的位置了）
            root = root.right;
        }
        return root.val;
    }
}
